package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * author: Mr.Du
 * Date: 2023/12/15
 * Time: 14:58
 */
public class ReverseOddLevels {

    public static void main(String[] args) {
        CreateTree createTree = new CreateTree();
        TreeNode treeNode = createTree.constructTree(7);
        ReverseOddLevels reverseOddLevels = new ReverseOddLevels();
        TreeNode root = reverseOddLevels.reverseOddLevels(treeNode);
        createTree.cengxu(root);
    }

    public TreeNode reverseOddLevels1(TreeNode root) {
        if(root.left != null) dfs(root.left, root.right, true);
        return root;
    }

    public void dfs(TreeNode left, TreeNode right, boolean flag){
        if(left == null || right == null) return;
        if(flag){
            int tmp = left.val;
            left.val = right.val;
            right.val = tmp;
        }
        dfs(left.left, right.right, !flag);
        dfs(left.right, right.left, !flag);
    }

    public TreeNode reverseOddLevels(TreeNode root) {
        List<Integer> list = levelOrder(root);
        return constructTree(list);
    }

    public TreeNode constructTree(List<Integer> list) {
        int n = list.size();
        if (n == 0) {
            return null;
        }

        // 创建节点数组
        TreeNode[] nodes = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(list.get(i));
        }

        // 构建二叉树
        for (int i = 0; i < n; i++) {
            if (2 * i + 1 < n) {
                nodes[i].left = nodes[2 * i + 1];
            }
            if (2 * i + 2 < n) {
                nodes[i].right = nodes[2 * i + 2];
            }
        }

        // 返回根节点
        return nodes[0];
    }

    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int j = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i < sz;i++){
                root = queue.poll();
                list.add(root.val);
                if(root.left != null){
                    queue.offer(root.left);
                }
                if(root.right != null){
                    queue.offer(root.right);
                }
            }
            if(j % 2 != 0) Collections.reverse(list);
            res.addAll(list);
            j++;
        }
        return res;
    }
}
